#include "math.h"

using namespace std;

class Solution {
public:
    // 法一：袖珍计算器法
    // sqrt(x) = exp(0.5 * log(x))
    int mySqrt_TinyCalc(int x) {
        if (x == 0) return 0;
        int ans = exp(0.5 * log(x));
        return (long long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }

    // 法二：二分查找
    int mySqrt_BinarySearch(int x) {
        int l = 0, r = x, ans = -1;  // 非负整数从0开始！！！
        while (l <= r) {
            int mid = (l + r) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    // 法三：牛顿迭代法
    int mySqrt_NewtonMethod(int x) {
        if (x == 0) return 0;
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) break;
            x0 = xi;
        }
        return int(x0);
    }
};
